/*
 * @Description: 算法出自：https://www.gamedev.net/reference/articles/article2003.asp
 * @Author: Niezl
 * @Gitee: https://gitee.com/Morphlng
 * @Date: 2021-04-07 08:08:02
 * @LastEditors: Niezl
 * @LastEditTime: 2021-04-08 09:22:07
 */
#include <iostream>
#include "Map.h"
using namespace std;

// 初始化，返回Map，修改source、destination和box
Map Initialize(Vec2 &source, Vec2 &destination, Vec2 &box)
{
    int n, m;
    cout << "请输入地图大小：N*M" << endl;
    cin >> n >> m;
    cout << "请输入地图：'.'表示空地，'X'表示玩家，'*'表示箱子，'#'表示障碍物，'@'表示终点" << endl;
    vector<vector<char>> signs;
    for (int i = 0; i < n; i++)
    {
        vector<char> tmp;
        for (int j = 0; j < m; j++)
        {
            char ch;
            cin >> ch;
            tmp.push_back(ch);
        }
        signs.push_back(tmp);
    }

    Map map;
    map.setWorldSize(Vec2(n, m));
    map.setDiagonalMovement(false);

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            switch (signs[i][j])
            {
            case '#':
                map.addCollision({i, j});
                break;
            case 'X':
            case 'x':
                source.x = i, source.y = j;
                break;
            case '@':
                destination.x = i, destination.y = j;
                break;
            case '*':
                box.x = i, box.y = j;
                break;
            default:
                break;
            }
        }

    return map;
}

// 求箱子移动一步的相反方向，人应该移动至此方能推动
Vec2 opposite(Vec2 last_pos, Vec2 next_pos)
{
    int deltax = next_pos.x - last_pos.x;
    int deltay = next_pos.y - last_pos.y;

    return Vec2(deltax == 0 ? last_pos.x : last_pos.x - deltax, deltay == 0 ? last_pos.y : last_pos.y - deltay);
}

bool exist_Path(Map map, const CoordinateList &path, Vec2 source, const Vec2 &destination)
{
    if (path.empty())
        return false;

    Vec2 man_pos = source; // 初始时，人在起始位置
    int distance = 0;
    for (CoordinateList::const_reverse_iterator it = path.rbegin() + 1; it != path.rend(); it++)
    {
        Vec2 needToGo = opposite(*(it - 1), *it);         // 为了将箱子推到(*it)所在，人需要在的位置
        map.addCollision(Vec2((it - 1)->x, (it - 1)->y)); // 暂时的将箱子所在位置设为障碍物
        CoordinateList tmp = map.findPath(man_pos, needToGo);

        if (tmp.empty())
            return false;
        distance += tmp.size();
        map.removeCollision(Vec2((it - 1)->x, (it - 1)->y));
        man_pos = *(it - 1);
    }
    cout << "distance=" << distance << endl;
    return true;
}

/*
Example 1：
4 4
. . . .
. . * @
. . . .
. X . .

Example 2:
6 6
. . . # . .
. . . . . .
# * # # . .
. . # . # .
. . X . . .
. @ # . . .
*/

int main()
{
    Vec2 source, destination, box;
    Map map = Initialize(source, destination, box);

    cout << "Generate path ... \n";
    CoordinateList path = map.findPath(box, destination);

    cout << "path:" << endl;
    for (CoordinateList::reverse_iterator it = path.rbegin(); it != path.rend(); it++)
    {
        cout << it->x << " " << it->y << "\n";
    }

    if (exist_Path(map, path, source, destination))
    {
        cout << "可以成功推箱子！" << endl;
    }
    else
        cout << "无法将箱子推至终点！" << endl;

    return 0;
}